package day31;

/**
 * @author aiPlusPlus
 * @version 1.0
 * @date 2023/1/31 17:08
 */

import java.util.LinkedList;
import java.util.Queue;

/**
 * 给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
 *
 * 两个相邻元素间的距离为 1 。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
 * 输出：[[0,0,0],[0,1,0],[0,0,0]]
 * 示例 2：
 *
 *
 *
 * 输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
 * 输出：[[0,0,0],[0,1,0],[1,2,1]]
 */
public class Solution7 {
    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int [][]dirt=new int[m][n];
        Queue<int[]> queue=new LinkedList<>();
        boolean [][]see=new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(mat[i][j]==0){
                    queue.offer(new int[]{i,j});
                    see[i][j]=true;
                }
            }
        }
        while (!queue.isEmpty()){
            int[] poll = queue.poll();
            int i = poll[0];
            int j = poll[1];
            for (int d = 0; d < 4; d++) {
                int ni = i+dirs[d][0];
                int nj = j+dirs[d][1];
                if(ni >= 0 && ni < m && nj >= 0 && nj < n && !see[ni][nj]){
                    dirt[ni][nj]=dirt[i][j]+1;
                    queue.offer(new int[]{ni, nj});
                    see[ni][nj]=true;
                }
            }
        }
        return dirt;
    }
}
